package 记忆化搜索;

import 二叉树.TreeNode;

import java.util.HashMap;

//337 打家劫舍3 （这题想通不难，难的是代码的简洁化，以及不使用缓存数组了，换用hashmap）
public class Solution3 {
    public int rob(TreeNode root) {
        return dfs(root);
    }
    HashMap<TreeNode,Integer> mem = new HashMap();
    private int dfs(TreeNode node) {
        if (node == null) return 0;
        if (mem.containsKey(node)) return mem.get(node);
        //选
        int lf = 0,rt = 0;
        if (node.left != null) lf = dfs(node.left.left) + dfs(node.left.right);
        if (node.right != null) rt = dfs(node.right.left) + dfs(node.right.right);
        int select = node.val + lf + rt;
        //不选
        int unselect = dfs(node.left) + dfs(node.right);
        int ans = Math.max(select,unselect);
        mem.put(node,ans);
        return ans;
    }
}
